#include <stdio.h>
#include <stdlib.h>

// 二叉树结点结构
typedef struct BSTNode
{
    int data;              // 数据域
    struct BSTNode *left;  // 左子树指针
    struct BSTNode *right; // 右子树指针
} BSTNode, *BSTree;

// 1. 初始树（创建空树）
void InitBST(BSTree *T)
{
    *T = NULL;
}

// 2. 销毁树（递归释放所有结点）
void DestroyBST(BSTree *T)
{
    if (*T)
    {
        DestroyBST(&(*T)->left);
        DestroyBST(&(*T)->right);
        free(*T);
        *T = NULL;
    }
}

// 3. 插入结点（递归实现）
bool InsertBST(BSTree *T, int value)
{
    if (*T == NULL)
    {
        BSTNode *newNode = (BSTNode *)malloc(sizeof(BSTNode));
        if (!newNode)
            return false;
        newNode->data = value;
        newNode->left = newNode->right = NULL;
        *T = newNode;
        return true;
    }

    if (value < (*T)->data)
    {
        return InsertBST(&(*T)->left, value);
    }
    else if (value > (*T)->data)
    {
        return InsertBST(&(*T)->right, value);
    }

    return false; // 值已存在
}

// 4. 查找结点（递归实现）
BSTNode *SearchBST(BSTree T, int value)
{
    if (T == NULL)
        return NULL;

    if (value < T->data)
    {
        return SearchBST(T->left, value);
    }
    else if (value > T->data)
    {
        return SearchBST(T->right, value);
    }

    return T; // 找到
}

// 找到子树中的最小值结点（用于删除操作）
BSTNode *FindMin(BSTNode *node)
{
    while (node && node->left)
    {
        node = node->left;
    }
    return node;
}

// 5. 删除结点（递归实现）
bool DeleteBST(BSTree *T, int value)
{
    if (*T == NULL)
        return false;

    if (value < (*T)->data)
    {
        return DeleteBST(&(*T)->left, value);
    }
    else if (value > (*T)->data)
    {
        return DeleteBST(&(*T)->right, value);
    }
    else
    {
        // 找到要删除的结点
        if ((*T)->left == NULL)
        {
            BSTNode *temp = (*T)->right;
            free(*T);
            *T = temp;
        }
        else if ((*T)->right == NULL)
        {
            BSTNode *temp = (*T)->left;
            free(*T);
            *T = temp;
        }
        else
        {
            // 有两个子结点：用右子树的最小值替换
            BSTNode *temp = FindMin((*T)->right);
            (*T)->data = temp->data;
            DeleteBST(&(*T)->right, temp->data);
        }
        return true;
    }
}

// 中序遍历（用于测试）
void InOrderTraversal(BSTree T)
{
    if (T)
    {
        InOrderTraversal(T->left);
        printf("%d ", T->data);
        InOrderTraversal(T->right);
    }
}

int main()
{
    BSTree tree;
    InitBST(&tree);

    // 插入测试
    InsertBST(&tree, 50);
    InsertBST(&tree, 30);
    InsertBST(&tree, 70);
    InsertBST(&tree, 20);
    InsertBST(&tree, 40);
    InsertBST(&tree, 60);
    InsertBST(&tree, 80);

    printf("BST after insertion: ");
    InOrderTraversal(tree);
    printf("\n");

    // 查找测试
    int searchVal = 40;
    BSTNode *found = SearchBST(tree, searchVal);
    printf("%d %s found in BST\n", searchVal, found ? "is" : "is not");

    // 删除测试
    DeleteBST(&tree, 30);
    printf("BST after deleting 30: ");
    InOrderTraversal(tree);
    printf("\n");

    // 销毁树
    DestroyBST(&tree);
    printf("BST after destruction: ");
    InOrderTraversal(tree);
    printf("\n");

    return 0;
}